import functools


class Solution(object):
    def shortestPathAllKeys(self, grid):
        m, n = len(grid), len(grid[0])
        keys = {}
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '@':
                    start = (i, j)
                if 'a' <= grid[i][j] <= 'f':
                    keys[ord(grid[i][j]) - ord('a')] = (i, j)
        len_keys = len(keys)

        @functools.cache
        def search(last_node, val, next_node):
            now = {last_node}
            already = {last_node}
            dist = 0
            while now:
                dist += 1
                next_st = set()
                for x, y in now:
                    for ux, uy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                        if 0 <= ux < m and 0 <= uy < n and (ux, uy) not in already:
                            if grid[ux][uy] in ['.', '@'] or 'a' <= grid[ux][uy] <= 'f' or (
                                    'A' <= grid[ux][uy] <= 'F' and (val >> (ord(grid[ux][uy]) - ord('A'))) & 1):
                                already.add((ux, uy))
                                next_st.add((ux, uy))
                                if (ux, uy) == next_node:
                                    return dist
                now = next_st
            return float('inf')

        @functools.cache
        def dfs(val, p):
            last_val = val ^ (1 << p)
            if last_val == 0:
                last_node = start
                return search(last_node, last_val, keys[p])
            else:
                min_step = float('inf')
                for i in range(len_keys):
                    if (last_val >> i) & 1:
                        min_step = min(min_step, search(keys[i], last_val, keys[p]) + dfs(last_val, i))
                return min_step

        ans = float('inf')
        for i in range(len_keys):
            ans = min(ans, dfs((1 << len_keys) - 1, i))
        if ans < float('inf'):
            return ans
        else:
            return -1


data = Solution()
grid = ["@.a.#", "###.#", "b.A.B"]
print(data.shortestPathAllKeys(grid))
grid = ["@..aA", "..B#.", "....b"]
print(data.shortestPathAllKeys(grid))
grid = ["@Aa"]
print(data.shortestPathAllKeys(grid))
